Crate cranelift_entity

Array-based data structures using densely numbered entity references as mapping keys.

This crate defines a number of data structures based on arrays. The arrays are not indexed by usize as usual, but by entity references which are integers wrapped in new-types. This has a couple advantages:

• Improved type safety. The various map and set types accept a specific key type, so there is no confusion about the meaning of an array index, as there is with plain arrays.
• Smaller indexes. The normal usize index is often 64 bits which is way too large for most purposes. The entity reference types can be smaller, allowing for more compact data structures.

The EntityRef trait should be implemented by types to be used as indexed. The entity_impl! macro provides convenient defaults for types wrapping u32 which is common.

• PrimaryMap is used to keep track of a vector of entities, assigning a unique entity reference to each.
• SecondaryMap is used to associate secondary information to an entity. The map is implemented as a simple vector, so it does not keep track of which entities have been inserted. Instead, any unknown entities map to the default value.
• SparseMap is used to associate secondary information to a small number of entities. It tracks accurately which entities have been inserted. This is a specialized data structure which can use a lot of memory, so read the documentation before using it.
• EntitySet is used to represent a secondary set of entities. The set is implemented as a simple vector, so it does not keep track of which entities have been inserted into the primary map. Instead, any unknown entities are not in the set.
• EntityList is a compact representation of lists of entity references allocated from an associated memory pool. It has a much smaller footprint than Vec.

Modules

• packed_option
  Compact representation of Option<T> for types with a reserved value.

Macros

• entity_impl
  Macro which provides the common implementation of a 32-bit entity reference.

Structs

• BoxedSlice
  A slice mapping K -> V allocating dense entity references.
• EntityList
  A small list of entity references allocated from a pool.
• EntitySet
  A set of K for densely indexed entity references.
• Iter
  Iterate over all keys in order.
• IterMut
  Iterate over all keys in order.
• Keys
  Iterate over all keys in order.
• ListPool
  A memory pool for storing lists of T.
• PrimaryMap
  A primary mapping K -> V allocating dense entity references.
• SecondaryMap
  A mapping K -> V for densely indexed entity references.
• SparseMap
  A sparse mapping of entity references.

Traits

• EntityRef
  A type wrapping a small integer index should implement EntityRef so it can be used as the key of an SecondaryMap or SparseMap.
• SparseMapValue
  Trait for extracting keys from values stored in a SparseMap.
• Unsigned
  Helper trait used to add unsigned() methods to primitive signed integer types.

Type Aliases

• SparseSet
  A sparse set of entity references.